1 /*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkNotNull;
20 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
21 import static com.google.common.collect.ObjectArrays.checkElementsNotNull;
22
23 import com.google.common.annotations.GwtCompatible;
24
25 import java.io.Serializable;
26 import java.util.AbstractCollection;
27 import java.util.Collection;
28 import java.util.Iterator;
29
30 import javax.annotation.Nullable;
31
32 /**
33 * An immutable collection. Does not permit null elements.
34 *
35 * <p>In addition to the {@link Collection} methods, this class has an {@link
36 * #asList()} method, which returns a list view of the collection's elements.
37 *
38 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed
39 * outside of this package as it has no public or protected constructors. Thus,
40 * instances of this type are guaranteed to be immutable.
41 *
42 * @author Jesse Wilson
43 * @since 2.0 (imported from Google Collections Library)
44 */
45 @GwtCompatible(emulated = true)
46 @SuppressWarnings("serial") // we're overriding default serialization
47 public abstract class ImmutableCollection<E> extends AbstractCollection<E>
48 implements Serializable {
49
50 ImmutableCollection() {}
51
52 /**
53 * Returns an unmodifiable iterator across the elements in this collection.
54 */
55 @Override
56 public abstract UnmodifiableIterator<E> iterator();
57
58 @Override
59 public final Object[] toArray() {
60 int size = size();
61 if (size == 0) {
62 return ObjectArrays.EMPTY_ARRAY;
63 }
64 Object[] result = new Object[size];
65 copyIntoArray(result, 0);
66 return result;
67 }
68
69 @Override
70 public final <T> T[] toArray(T[] other) {
71 checkNotNull(other);
72 int size = size();
73 if (other.length < size) {
74 other = ObjectArrays.newArray(other, size);
75 } else if (other.length > size) {
76 other[size] = null;
77 }
78 copyIntoArray(other, 0);
79 return other;
80 }
81
82 @Override
83 public boolean contains(@Nullable Object object) {
84 return object != null && super.contains(object);
85 }
86
87 /**
88 * Guaranteed to throw an exception and leave the collection unmodified.
89 *
90 * @throws UnsupportedOperationException always
91 * @deprecated Unsupported operation.
92 */
93 @Deprecated
94 @Override
95 public final boolean add(E e) {
96 throw new UnsupportedOperationException();
97 }
98
99 /**
100 * Guaranteed to throw an exception and leave the collection unmodified.
101 *
102 * @throws UnsupportedOperationException always
103 * @deprecated Unsupported operation.
104 */
105 @Deprecated
106 @Override
107 public final boolean remove(Object object) {
108 throw new UnsupportedOperationException();
109 }
110
111 /**
112 * Guaranteed to throw an exception and leave the collection unmodified.
113 *
114 * @throws UnsupportedOperationException always
115 * @deprecated Unsupported operation.
116 */
117 @Deprecated
118 @Override
119 public final boolean addAll(Collection<? extends E> newElements) {
120 throw new UnsupportedOperationException();
121 }
122
123 /**
124 * Guaranteed to throw an exception and leave the collection unmodified.
125 *
126 * @throws UnsupportedOperationException always
127 * @deprecated Unsupported operation.
128 */
129 @Deprecated
130 @Override
131 public final boolean removeAll(Collection<?> oldElements) {
132 throw new UnsupportedOperationException();
133 }
134
135 /**
136 * Guaranteed to throw an exception and leave the collection unmodified.
137 *
138 * @throws UnsupportedOperationException always
139 * @deprecated Unsupported operation.
140 */
141 @Deprecated
142 @Override
143 public final boolean retainAll(Collection<?> elementsToKeep) {
144 throw new UnsupportedOperationException();
145 }
146
147 /**
148 * Guaranteed to throw an exception and leave the collection unmodified.
149 *
150 * @throws UnsupportedOperationException always
151 * @deprecated Unsupported operation.
152 */
153 @Deprecated
154 @Override
155 public final void clear() {
156 throw new UnsupportedOperationException();
157 }
158
159 /*
160 * TODO(kevinb): Restructure code so ImmutableList doesn't contain this
161 * variable, which it doesn't use.
162 */
163 private transient ImmutableList<E> asList;
164
165 /**
166 * Returns a list view of the collection.
167 *
168 * @since 2.0
169 */
170 public ImmutableList<E> asList() {
171 ImmutableList<E> list = asList;
172 return (list == null) ? (asList = createAsList()) : list;
173 }
174
175 ImmutableList<E> createAsList() {
176 switch (size()) {
177 case 0:
178 return ImmutableList.of();
179 case 1:
180 return ImmutableList.of(iterator().next());
181 default:
182 return new RegularImmutableAsList<E>(this, toArray());
183 }
184 }
185
186 /**
187 * Returns {@code true} if this immutable collection's implementation contains references to
188 * user-created objects that aren't accessible via this collection's methods. This is generally
189 * used to determine whether {@code copyOf} implementations should make an explicit copy to avoid
190 * memory leaks.
191 */
192 abstract boolean isPartialView();
193
194 /**
195 * Copies the contents of this immutable collection into the specified array at the specified
196 * offset. Returns {@code offset + size()}.
197 */
198 int copyIntoArray(Object[] dst, int offset) {
199 for (E e : this) {
200 dst[offset++] = e;
201 }
202 return offset;
203 }
204
205 Object writeReplace() {
206 // We serialize by default to ImmutableList, the simplest thing that works.
207 return new ImmutableList.SerializedForm(toArray());
208 }
209
210 /**
211 * Abstract base class for builders of {@link ImmutableCollection} types.
212 *
213 * @since 10.0
214 */
215 public abstract static class Builder<E> {
216 static final int DEFAULT_INITIAL_CAPACITY = 4;
217
218 static int expandedCapacity(int oldCapacity, int minCapacity) {
219 if (minCapacity < 0) {
220 throw new AssertionError("cannot store more than MAX_VALUE elements");
221 }
222 // careful of overflow!
223 int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
224 if (newCapacity < minCapacity) {
225 newCapacity = Integer.highestOneBit(minCapacity - 1) << 1;
226 }
227 if (newCapacity < 0) {
228 newCapacity = Integer.MAX_VALUE;
229 // guaranteed to be >= newCapacity
230 }
231 return newCapacity;
232 }
233
234 Builder() {
235 }
236
237 /**
238 * Adds {@code element} to the {@code ImmutableCollection} being built.
239 *
240 * <p>Note that each builder class covariantly returns its own type from
241 * this method.
242 *
243 * @param element the element to add
244 * @return this {@code Builder} instance
245 * @throws NullPointerException if {@code element} is null
246 */
247 public abstract Builder<E> add(E element);
248
249 /**
250 * Adds each element of {@code elements} to the {@code ImmutableCollection}
251 * being built.
252 *
253 * <p>Note that each builder class overrides this method in order to
254 * covariantly return its own type.
255 *
256 * @param elements the elements to add
257 * @return this {@code Builder} instance
258 * @throws NullPointerException if {@code elements} is null or contains a
259 * null element
260 */
261 public Builder<E> add(E... elements) {
262 for (E element : elements) {
263 add(element);
264 }
265 return this;
266 }
267
268 /**
269 * Adds each element of {@code elements} to the {@code ImmutableCollection}
270 * being built.
271 *
272 * <p>Note that each builder class overrides this method in order to
273 * covariantly return its own type.
274 *
275 * @param elements the elements to add
276 * @return this {@code Builder} instance
277 * @throws NullPointerException if {@code elements} is null or contains a
278 * null element
279 */
280 public Builder<E> addAll(Iterable<? extends E> elements) {
281 for (E element : elements) {
282 add(element);
283 }
284 return this;
285 }
286
287 /**
288 * Adds each element of {@code elements} to the {@code ImmutableCollection}
289 * being built.
290 *
291 * <p>Note that each builder class overrides this method in order to
292 * covariantly return its own type.
293 *
294 * @param elements the elements to add
295 * @return this {@code Builder} instance
296 * @throws NullPointerException if {@code elements} is null or contains a
297 * null element
298 */
299 public Builder<E> addAll(Iterator<? extends E> elements) {
300 while (elements.hasNext()) {
301 add(elements.next());
302 }
303 return this;
304 }
305
306 /**
307 * Returns a newly-created {@code ImmutableCollection} of the appropriate
308 * type, containing the elements provided to this builder.
309 *
310 * <p>Note that each builder class covariantly returns the appropriate type
311 * of {@code ImmutableCollection} from this method.
312 */
313 public abstract ImmutableCollection<E> build();
314 }
315
316 abstract static class ArrayBasedBuilder<E> extends ImmutableCollection.Builder<E> {
317 Object[] contents;
318 int size;
319
320 ArrayBasedBuilder(int initialCapacity) {
321 checkNonnegative(initialCapacity, "initialCapacity");
322 this.contents = new Object[initialCapacity];
323 this.size = 0;
324 }
325
326 /**
327 * Expand the absolute capacity of the builder so it can accept at least
328 * the specified number of elements without being resized.
329 */
330 private void ensureCapacity(int minCapacity) {
331 if (contents.length < minCapacity) {
332 this.contents = ObjectArrays.arraysCopyOf(
333 this.contents, expandedCapacity(contents.length, minCapacity));
334 }
335 }
336
337 @Override
338 public ArrayBasedBuilder<E> add(E element) {
339 checkNotNull(element);
340 ensureCapacity(size + 1);
341 contents[size++] = element;
342 return this;
343 }
344
345 @Override
346 public Builder<E> add(E... elements) {
347 checkElementsNotNull(elements);
348 ensureCapacity(size + elements.length);
349 System.arraycopy(elements, 0, contents, size, elements.length);
350 size += elements.length;
351 return this;
352 }
353
354 @Override
355 public Builder<E> addAll(Iterable<? extends E> elements) {
356 if (elements instanceof Collection) {
357 Collection<?> collection = (Collection<?>) elements;
358 ensureCapacity(size + collection.size());
359 }
360 super.addAll(elements);
361 return this;
362 }
363 }
364 }